一個旅行者有一個最多能用m公斤的背包，現在有n件物品，它們的重量分别是w1，w2，...,wn,它們的價值分别為c1,c2,...,cn.若每種物品隻有一件求旅行者能獲得最大總價值。
輸入的第一行為t，表示測試資料的組數。對于每組測試資料的第一行：兩個整數，m(背包容量，m<=200)和n(物品數量，n<=30)，第2..n+1行：每行二個整數wi,ci，表示每個物品的重量和價值。
對于每組測試資料輸出僅一行，一個數，表示最大總價值。
#include<iostream>
#include<cstdio>
using namespace std;
int w[20],v[20],f[20];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(int j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
printf("%d",f[m]);
return 0;
//每一件物品的狀态抉擇為放還是不放 如果不放 前i件物品 不超過v的最大值就是前i-1件物品不超過v的最大值
否則 放就是 前i-1物品放入 v-w[i]的最大值加上要放入的目前的價值
優化 二維數組優化為一維數組 f[v]為重量不超過v的最大值
【代碼】
完全背包
二維
一維
資料 其實沒多大用這資料。。。。
01背包和完全背包的差別是完全背包每種物品有無數件 是以每次決策就改變了 不在是取或不取 而是取幾件、
分析一下代碼 發現兩個代碼很像 差別就是01背包體積循環是 v--1,而完全背包是1--v
why？
為什麼01逆序 完全順序
先講01如果順序後會怎樣呢？
我們知道f[v]=max(f[v],f[v-w[i]]+c[i]);如果順序1--v，因為f[v]是由f[v-w[i]]推過來的，如果順序的話 f[v-w[i]]一定推完了 我們可能在f[v-w[i]]時就已經
放入了i物品 ，是以你推的f[v]就拿了兩件i物品了，是以01要逆推，，，反之，，拿好幾件就是完全 順推了。。。。
我也剛懂。。。糊裡糊塗的。。。自己好好想想吧qaq