当前位置: 代码迷 >> 综合 >> 0-1背包问题:输出最小背包
  详细解决方案

0-1背包问题:输出最小背包

热度:7   发布时间:2024-01-18 23:44:03.0

如何输出最小背包?

0-1背包
#include <iostream>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int weight[maxn];
int value[maxn];
int n,v;
int max(int a,int b){if(a>b) return a;return b;
}
int main(int argc, char const *argv[])
{int T;cin>>T;while(T--){cin>>n>>v;for(int i=1;i<=n;i++){cin>>value[i];}for(int i=1;i<=n;i++){cin>>weight[i];}memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=v;j>=weight[i];j--){dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}int out=dp[1][v];for(int k=2;k<=n;k++)out = max(out,dp[k][v]);cout<<out<<endl;}/* code */return 0;
}



其中i表示放第i个物品,j表示背包所容纳的重量,那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品,刚开始接触会有疑问,tab[i-1][j-weight[i]]这个值,可以这样理解:tab[i-1][j]为装到上一个物品在背包j容量时的最佳值,那么如果我要求

  相关解决方案