【算法】背包问题

压缩为一维数组

#include<stdio.h>int main(){int n;int v;scanf("%d %d",&n,&v);int weight[1005];		//物品价值int value[1005]; for(int i=0;i<n;i++){scanf("%d %d",&weight[i],&value[i]);}int dp[1005]={0};for(int i=0;i<n;i++){		//物品 for(int j=v;j>=weight[i];j--){		//大小 	注意要倒序 dp[j]=dp[j]>(dp[j-weight[i]]+value[i])?dp[j]:(dp[j-weight[i]]+value[i]);//printf("j:%d dp[j]:%d i:%d\n",j,dp[j],i);}}printf("%d",dp[v]);
}

恰好装满的0-1背包

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){int n;int v;scanf("%d %d",&n,&v);int weight[1005];		//物品价值int value[1005]; for(int i=0;i<n;i++){scanf("%d %d",&weight[i],&value[i]);}int dp1[1005];memset(dp1,-1,sizeof(dp1));		//必须将初值赋为-1，且下标0为0 dp1[0]=0;for(int i=0;i<n;i++){		//物品 for(int j=v;j>=weight[i];j--){		//大小 	注意要倒序 且j要大于weight[i]if(dp1[j-weight[i]]!=-1)dp1[j]=dp1[j]>(dp1[j-weight[i]]+value[i])?dp1[j]:(dp1[j-weight[i]]+value[i]);//printf("j:%d dp[j]:%d i:%d\n",j,dp[j],i);}}if(dp1[v]==-1)printf("0");else	printf("%d",dp1[v]);
}

完全背包

#include<stdio.h>
#include<string.h>int main(){int n,v;scanf("%d %d",&n,&v);int weight[1005];int value[1005];for(int i=0;i<n;i++){scanf("%d %d",&weight[i],&value[i]);}int dp[1005]={0};int dp1[1005];memset(dp1,-1,sizeof(dp1));dp1[0]=0;for(int i=0;i<n;i++){for(int j=0;j<=v;j++){		//01背包为倒序，完全背包为正序 if(j>=weight[i]){dp[j]=dp[j]>(dp[j-weight[i]]+value[i])?dp[j]:(dp[j-weight[i]]+value[i]);if(dp1[j-weight[i]]!=-1){dp1[j]=dp1[j]>(dp1[j-weight[i]]+value[i])?dp1[j]:(dp1[j-weight[i]]+value[i]);}} }}printf("%d\n",dp[v]);if(dp1[v]==-1)printf("0");else	printf("%d",dp1[v]);
}

注意
先遍历物品在遍历背包得到的是组合数
也就是说{1,2}和{2,1}算同一种情况

for(int i=0;i<numsSize;i++){        //先遍历物品for(int j = nums[i];j<=target;j++){     //在遍历背包dp[j] +=dp[j-nums[i]];}}

先遍历背包在遍历物品得到的是排列数
也就是说{1,2}和{2,1}算两种情况

for(int i=0;i<=target;i++){        //先遍历背包for(int j = 0;j<=numsSize;j++){     //在遍历物品dp[i] +=dp[i-nums[j]];}}